Typed stack languages, such as Java® bytecode and Common Intermediate Language (CIL), typically have a last-in-first-out (LIFO) operand stack on which virtual machine (VM) instructions can save and retrieve operands. Each operand may be accompanied with its type information (e.g., reference or non-reference) when it is pushed onto the stack. A VM may use this type information to facilitate certain runtime services, such as execution-time type-safety verification, for example.
The type information may also be used during garbage collection (GC), for root set enumeration. Typically, the GC routine needs to check every operand on the stack, to determine whether the operand is a reference to an object in the managed heap. Operands that are not references to objects in the managed heap may be referred to as numeric or non-reference operands. Non-reference operands may be unimportant for GC, but operands that are references to objects are very important. All reference operands in the operand stack are typically treated as roots from which the GC routine performs object scanning.
If the GC routine can accurately determine the reference or non-reference property of each operand on the stack, the GC routine is considered accurate. For purposes of this disclosure, an operand is said to be of the “reference” type if the operand is a reference to an object, and to be of the “non-reference” type if the operand is not a reference to an object. To support accurate GC, each operand may be associated with a corresponding tag to indicate whether or not the operand is a reference to an object.
As described in greater detail below, conventional implementations for operand tags typically provide either space efficiency or computational efficiency. As recognized by the present invention, it would be beneficial to implement operand tags in a manner that increases the space efficiency, the computational efficiency, or both, relative to conventional techniques. It would also be beneficial if the implementations with increased efficiency could be used by routines for GC and/or other types of routines.